package easy._160_IntersectionofTwoLinkedLists;

import java.util.HashSet;
import java.util.Set;

public class IntersectionofTwoLinkedLists {
    //两个链表逐个加入set集合中，逐一判断是否重复，若重复则为相交首节点，速度较慢
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode beginA = headA;
        ListNode beginB = headB;
        Set<ListNode> nodes = new HashSet<ListNode>();
        while(beginA!=null || beginB!=null){
            if(beginA!=null){
                if(nodes.contains((beginA))){
                    return beginA;
                }
                nodes.add(beginA);
                beginA = beginA.next;
            }
            if(beginB!=null){
                if(nodes.contains(beginB)){
                    return beginB;
                }
                nodes.add(beginB);
                beginB = beginB.next;
            }
        }
        return null;
    }
    //对A和B分别遍历A+B和B+A，如果A和B有交集，则A与B一定在路程中相交
    public ListNode getIntersectionNode1(ListNode headA,ListNode headB){
        if(headA==null || headB==null) return null;
        ListNode beginA = headA;
        ListNode beginB = headB;
        while(beginA!=beginB){
            beginA = beginA==null ? headB:beginA.next;
            beginB = beginB==null ? headA:beginB.next;
        }
        return beginA;
    }
}
